Łamanie szyfru XOR

Darek Mleczak - 15 Lis 2003, 04:54

Witam.

następująco:
Mamy tekst jawny (ciąg bajtów) oraz klucz (o dowolnej dlugosci). Sumujemy
modulo2 bajt tekstu jawnego z bajtem klucza i uzyskujemy bajt kryptogramu.
Klucza uzywamy cyklicznie w calej operacji szyfrowania (kazda kolejna
operacja XOR odbywa sie z nastepnym bajtem klucza, gdy dojdziemy do
ostatniego bajtu klucza wracamy na jego poczatek)

I teraz mając tak zaszyfrowany text musimy złamać szyfr... W internecie
znalazlem cos na temat metody zwanej zliczaniem koimcydencji... Jednak nie
bardzo to rozumiem. Czy ktos dysponujue moze jakimis materialami na ten
temat lub mógłby opisać kolejne kroki algorytmu. Bede wdzięczny za
jakąkolwiek pomoc

Jacek Popławski - 15 Lis 2003, 05:22

Modulo2 _bajt_? To oprócz szyfrowania masz tu niezłą kompresję, bo z 8 bitów
robi się 1.

Bartosz Otwocki - 16 Lis 2003, 09:05

Sprawa przedstawia sie w nastepujacy sposob. Rzeczyiscie najbardziej
uniwersalna metoda jest zastosowanie koincydencji znakow. Koincydencja
znakow jest obliczana na podstawie dwoch textow, w ktorych porownujemy
ilosc powtarzajacych sie znakow. Porownujemy tylko te znaki ze soba
ktore sa na tych samych pozycjach w oby textach. Teraz liczymy ile sie
powtorzylo znakow i stosunek ilosci powtarzajacych sie znakow do
ilosci znakow w tekscie daje koincydencje. Z pewnych matematycznych
zalozen wynika, ze koincydencje mozna policzyc rowniez jako sume
kwadratow prawdopodobienstw wystapienia w tekscie pojedynczych znakow.
Teraz najlepszy myk, okazuje sie, ze koincydencja w tekscie
przesunietym o n pozycji w stosunku do tekstu nie przesunietego ale
mniejszego niz dlugosc klucza jest znaczaco inna (bliska tekstowi
losowemu). Ta cecha pozwala nam na znalezienie dlugosci klucza.

jezyku co szyfrogram. Powiedzmy ze szyfrogram powstal na skutek
zaszyfrowania kodu zrodlowego programu, wiec musimy znalezc dowolny
kod zrodlowy i policzyc dla niego koincydencje znakow. A wiec
sprawdzamy czestotliwosci wystepowania w tym tekscie poszczegolnych
znakow podnosimy to do kwadratu i sumujemy ze soba. To bedzie wzorcowa
koincydencja. Teraz bierzemy kryptogram (najlepiej jakis wycinek) i
przesuwamy go wzgledem siebie cyklicznie badajac kaincydencje znakow.
W pewnym momencie koincydencja znakow przesuwanego wzgledem siebie
kryptogramu i koincydencja wzorcowa prawie sie pokryja. A jesli tak
sie stanie to mamy dlugosc klucza (ilosc przesuniec).

Najwazniejsze za nami. Teraz majac dlugosc klucza dzielimy kryptogram
na grupy znakow, ktore zostaly zaszyfrowane tym samym znakiem klucza.
W kazdej z takich grup badamy czestotliwosc wystepowania znakow ten
znak ktory wystepuje najczesciej odpowiada znakowi, ktory wystepowal
najczesciej w tekscie wzorcowym. Jako ze xor jest odwracalny to jak
zxorujesz znak z kryptogramu i znak z textu jawnego to otrzymasz znak
klucza. Operacje trzeba powtorzyc tyle razy ile jest znakow klucza.

Metoda, ktora opisalem nazywa sie statystyczna i konieczne jest aby
operacje przeprowadzac na stosunkowo dlugich textach bo przy krotkich
metoda ta nie zadziala.

PS. Pan Jacek P. to taki grupowy rozweselacz co to nic nie umie ale ma
duzo dobrego humoru, wiec nie przejmuj sie jego komentarzami.

Marcin Wojtczuk - 16 Lis 2003, 13:34

Bartosz Otwocki claimed:
[ciach]

Wielkie dzięki, świetna zachęta żeby poczytać coś więcej.

Darek Mleczak - 17 Lis 2003, 04:17

Dziekuje za wyjasnienie... teraz juz mam jasniejszy obraz jak to robic...
Ale mam jeszcze jedno pytanko.
Chodzi mi o wyznaczanie koinczydencji wzorcowej... Robie ststystyke tekstu
czyli zliczam ilosc wystapien znakow w tekscie i zapisuje sobie do tablicy
(kazdy element przechowuje ilsc wystapien jednego znaku)... i teraz nie wiem
czy dobrze rozumiem ale... musze kazdy element podniesc do kwadratu a potem
zsumowac wartosc wszystkich elementow tablicy tak? I ta suma to wartosc
koincydencji wzorcowej?
Teraz majac ta wartosc biore kryptogram i licze koincydencje z krytogramem
przsuwanym cyklicznie... tzn przesuwam znaki w kryptogramie o 1,2,3 itd
pozycje i licze koincydencje sprawdzajac czy na odpowiadajacych sobie
pozycjach kryptogramu i kryptogramu przesunietego sa takie same znaki. Ilosc
zgodnosci to wartosc koincydencji... Jesli wartosc jest rowna koincydencji
wzorcowej to mam dlugosc klucza okreslona przes ilosc przesuniec kryptogramu
tak.
Przepraszam ze jeszcze zawracam glowe ale wole sie upewnic czy dobrze
rozumuje, a nie moge sprawdzic bo akurat jestem w pracy.
Dziekuje za wszelkie sugestie i podpowiedzi

Bartosz Otwocki - 17 Lis 2003, 11:00

Nie calkiem. Nalezy zliczyc ile razy wystapil znak w tekscie oraz ile
jest wszystkich znakow w tekscie. Nastepnie ilosc wystapien danego
znaku podzielona przez ilosc znakow w tekscie podnosimy do kwadratu i
sumujemy z analogicznie policzonymi czestosciami dla innych znakow.

Tak policzona wartosc nalezy podzielic przez ilosc znakow i to dopiero
jest koincydencja.

Tak, ale najlepiej dopuscic jakis przedzial powiedzmy +-0,01 wokol
koincydencji wzorcowej.

Spox, no problem.

Darek Mleczak - 18 Lis 2003, 11:01

Przepraszam ze jeszcze mecze ale czy moglbys wyjasnic mi jeszcze ten
fragment? Jakos nie moge tego do konca zrozumieć... Ewentualnie jesli
dysponujesz jakimis materialami na ten temat bylbym batdzo wdzieczny.

Bartosz Otwocki - 18 Lis 2003, 11:38

Zaluzmy ze klucz ma 4 znaki. Caly kryptogram nalezy wtedy podzielic na
4 grupy w ktorych znajda sie znaki kryptogramu do ktorych
zaszyfrowania zastosowano ten sam znak klucza. Czyli grupa 1 bedzie
zawierac bajty 1,5,9 itd, grupa druga bajty 2,6,10 itd, grupa trzecia
bajty 3,7,11 itd., grupa czwarta bajty 4,8,12 itd.

Teraz w tych grupach trzeba zbadac czestosc wystepowania znakow, ten
ktory wystepuje najczesciej jest zaszyfrowana wersja najczesciej
wystepujacego znaku w tekscie wzorcowym.

Robert Święcki - 18 Lis 2003, 17:07

statystycznej, bierzesz najczęstsze trigramy w danym jezyku, w angielskim
to "ING" w polskim nie pamietam - "SIĘ?" czy cuś?? Teraz znasz
statystyczną częstotliwość takiego trigramu w danym języku i znasz w
tekście (będzie to najczęstrzy trigram). Dzielisz pierwszą liczbę przez
drugą i masz długośc klucza.

Jak masz dlugośc klucza to ponoć fraszka.. na poczatek odkodowujesz
pierwszy trigram, i masz trzy bajty klucza... dalej zasnąłem na wykładzie
z ochrony informacji w sieci, więc musisz sam poszukać (mozliwe, że
bierzesz drugi pod względem częstości... itd).

Bartosz Otwocki - 19 Lis 2003, 11:18

Ta metoda nazywa sie metoda Kasiskiego i jest malo skuteczna.

Robert Święcki - 23 Lis 2003, 08:38

Dobrze, obiecuję więcej nie zasypiać ;))

Tak bajde łej, chodzę na wykłady do świetnego specjelisty od krytografii,
dr Kossowski (członek PKN, IEEE i czegoś tam jeszcze)..

w każdym razie wykład przebiega np przykład tak:

"No więc dzisiaj to opowiemy sobie o DESie, DES jest już relatywnie starym
szyfrem, .. a czy wiecie że na ławeczce wyciskam 140kg .., no więc ten
DES to..."

Robert Święcki - 23 Lis 2003, 08:38

Dobrze, obiecuję więcej nie zasypiać ;))

Tak bajde łej, chodzę na wykłady do świetnego specjelisty od krytografii,
dr Kossowski (członek PKN, IEEE i czegoś tam jeszcze)..

w każdym razie wykład przebiega np. tak:

"No więc dzisiaj to opowiemy sobie o DESie, DES jest już relatywnie starym
szyfrem, .. a czy wiecie że na ławeczce wyciskam 140kg .., no więc ten
DES to..."